let {rand,stime} =require ("./fun");
let n=100000
let arr=rand(n)
function gb(arr,l,r){
    //递归借宿条件
    if(l>=r) return   //判断条件可以优化
    //划分左右两边
    let mid=~~((l+r)/2)
    //递归划分  直到划分成l>=r时
    gb(arr,l,mid)
    gb(arr,mid+1,r)

    //只有左边》右边时才交换数据   （从小到大排序时
    if(arr[mid]>arr[mid+1]){
        merge(arr,l,r,mid)
    }
}

function merge(arr,l,r,mid){
  let newa=[]
  //左右指针
  let i=l,j=mid+1

  //复制一份新数组段
  for(let g=l;g<=r;g++){
    newa[g-l]=arr[g]
  }
//   console.log(newa,'////')
  //开始从左右边提取值  
  //左边小 提取arr[左] 左下标++    i
  //右边小 提取arr[右] 右下标++    j
 for(let k=l;k<=r;k++){
     if(i>mid){
        arr[k]=newa[j-l]
        j++
     }else if(j>r){
        arr[k]=newa[i-l]
        i++
     }else if(newa[i-l]>newa[j-l]){
        arr[k]=newa[j-l]
         j++
     }else{
        arr[k]=newa[i-l]
        i++
     }
 }

}


// stime(gb,arr,0,n-1)
// console.log(arr.slice(n-10,n))
//n=100      0ms
//n=1000     4ms
//n=10000    12ms
//n=100000   54ms


//向上归并排序
function gb2(arr,n){
    for(let s=1;s<=n;s+=s){
        for(let i=0;i+s<n;i+=s+s){
            
            if(arr[i+s-1]>arr[i+s]){
                merge(arr,i,Math.min(i+2*s-1,n-1),i+s-1)
            }
        }
    }
}
 stime(gb2,arr,n)
 console.log(arr.slice(n-10,n))
 
//n=100      1ms
//n=1000     3ms
//n=10000    19ms
//n=100000   71ms